package com.zl.sort;

import com.zl.utils.SortTestHelper;

import java.lang.reflect.WildcardType;
import java.security.spec.ECField;

/**
 * @author zengle
 * @create 2021-05-24 8:32
 */
public class Sort {
    /**
     * 功能:选择排序
     *
     * @param arr
     */
    public void selectSort(int[] arr) {
        int n = arr.length, min;
        for (int i = 0; i < n - 1; i++) {
            /*要选择的次数:下标：0~n-2，共n-1次*/
            min = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min]) {
                    /*如果后面的数比前面的小,则记下它的下标*/
                    min = j;
                }
            }
            if (min != i) {
                /*如果min在循环中改变了,就需要交换数据*/
                exchange(arr, min, i);
            }
        }
    }

    private static void exchange(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    /**
     * 功能:直接插入排序
     *
     * @param arr
     */
    public void insertSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            /*要选择的次数:下标1~n-1，共n-1次*/
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[j + 1]) {
                    exchange(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 功能:冒泡排序
     *
     * @param arr
     */
    public void bubbleSort1(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) { // n-1；轮    1 -- n-1
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    exchange(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 优化：记录最后下沉位置，之后的肯定有序
     *
     * @param arr
     */
    public void bubbleSort2(int[] arr) {
        int k = 0, j;
        for (int i = arr.length - 1; i > 0; i = k) { //
            for (j = 0, k = 0; j < i; j++) {
                /*每次预置k=0,循环扫描后更新k*/
                if (arr[j] > arr[j + 1]) {
                    exchange(arr, j, j + 1);
                    k = j;
                }
            }
        }
    }

    /**
     * 功能:希尔排序
     *
     * @param arr
     */
    public void shellSort1(int[] arr) {

        int n = arr.length;
        for (int d = n / 2; d > 0; d /= 2) { // 分成  n/2  份
            for (int i = d; i < n; i++) { // 比较 n-d 趟
                for (int j = i; j >= d && arr[j] > arr[j - d]; j -= d) { //
                    // 前一个数大于后一个数
                    exchange(arr, j, j - d);
                }
            }
        }
    }

    public void shellSort2(int[] arr) {
        int d = 1;
        while (d < arr.length / 3) {
            d = d * 3 + 1;
        }

        int n = arr.length;
        for (; d > 0; d /= 3) { // 分成  n/3  份
            for (int i = d; i < n; i++) { // 比较 n-d 趟
                for (int j = i; j >= d && arr[j] < arr[j - d]; j -= d) { //
                    // 前一个数大于后一个数
                    exchange(arr, j, j - d);
                }
            }
        }
    }

    /**
     * 功能:快速排序
     *
     * @param arr
     */
    public void quickSort(int[] arr, int left, int right) {
        if (left >= right || arr.length < 2) {
            return;
        }
        int pivot = partision1(arr, left, right);
        if (left < right) {
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }

    private int partision1(int[] arr, int left, int right) {
        int low = left, high = right;
        int tmp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = tmp;

        return low;
    }

    private int partision2(int[] arr, int left, int right) {
        int less = left - 1, more = right;
        while (left < more) {
            if (arr[left] < arr[right]) {
                exchange(arr, ++less, left++);
            } else if (arr[left] > arr[right]) {
                exchange(arr, --more, left);
            } else {
                left++;
            }
        }
        exchange(arr, more, right);
        return more;
    }

    /**
     * 功能:堆排序
     *
     * @param arr
     */
    public void heapSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }
        heapInsert(arr);
        int len = arr.length - 1;
        while (len > 0) {
            exchange(arr, 0, len);
            heapify(arr, 0, --len);
        }
    }

    private void heapify(int[] arr, int index, int len) {
        int left = (index << 1) + 1;
        int right = left + 1;
        int largest = left;
        if (left > len) return;
        if (right <= len && arr[right] > arr[left]) {
            largest = right;
        }
        if (arr[largest] > arr[index]) {
            exchange(arr, largest, index);
            heapify(arr, largest, len);
        }
    }

    /*
     *  第一步：将数组堆化
     *  beginIndex = 第一个非叶子节点。
     *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
     *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
     */
    private void heapInsert(int[] arr) {
        int last = arr.length - 1;
        int begin = (last - 1) / 2;
        for (int i = begin; i >= 0; i--) {
            heapify(arr, i, last); // 大根堆
        }
    }

    /**
     * 归并排序
     *
     * @param arr
     */
    public void mergeSort(int[] arr) {
        int[] tmp = new int[arr.length];
        internalMergeSort(arr, tmp, 0, arr.length - 1);
    }

    private void internalMergeSort(int[] arr, int[] tmp, int left, int right) {

        if (left < right) {
            int mid = (left + right) / 2;
            internalMergeSort(arr, tmp, left, mid);
            internalMergeSort(arr, tmp, mid + 1, right);
            mergeSortedArray(arr, tmp, left, mid, right);
        }
    }

    private void mergeSortedArray(int[] arr, int[] tmp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        for (int p = 0; p < k; p++) {
            arr[left + p] = tmp[p];
        }
    }

    public static void main(String[] args) {
        int N = 20000;
        N = 20;
        Sort sort = new Sort();
        int[] arr = SortTestHelper.generateRandomArray(N, 0, 100);
        sort.mergeSort(arr);
        SortTestHelper.printArray(arr);

    }
}
